package main.java.indi.zyj.c150.bfs;

import java.util.*;

public class _03_SlidingPuzzle {

    public int slidingPuzzle(int[][] board) {

        int m = 2, n = 3;
        String target = "123450";

        int[][] neighbor = new int[][]{
                {1, 3},
                {0, 4, 2},
                {1, 5},
                {0, 4},
                {3, 1, 5},
                {4, 2}
        };

        StringBuilder s = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                s.append(board[i][j]);
            }
        }

        String init = s.toString();

        Queue<String> treeNodeQueueueue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        treeNodeQueueueue.offer(init);
        visited.add(init);
        int dpth = 0;

        while (!treeNodeQueueueue.isEmpty()) {

            int queueSize = treeNodeQueueueue.size();

            for (int i = 0; i < queueSize; i++) {

                String cur = treeNodeQueueueue.poll();

                if (cur.equals(target)) {
                    return dpth;
                }
                int idx = 0;
                for (; cur.charAt(idx) != '0'; idx++);
                for (int adj : neighbor[idx]) {
                    String new_board = swap(cur.toCharArray(), idx, adj);
                    // 防止走回头路
                    if (!visited.contains(new_board)) {
                        treeNodeQueueueue.offer(new_board);
                        visited.add(new_board);
                    }
                }
            }
            dpth++;
        }
        return -1;
    }

    private String swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }


}
